/*
 * tabu.java
 *
 * Created on 7 December, 2008, 12:36 AM
 *@author Pranay
 *
 * To change this template, choose Tools | Template Manager
 * and open the template in the editor.
 */

package vrp;

import java.util.LinkedList;

/**
 * 
 * @author Pranay
 */
public class Tabu {
	private int iters = 0;
	private double minCost = Double.MAX_VALUE;
	private double minLength = Double.MAX_VALUE;
	private Solution currentSol;
	private LinkedList<Move> tabuList = new LinkedList<Move>();
	
	/**
	 * List containing for each iteration the current solution's length
	 */
	private LinkedList<Double> currentSolutionsLength;
	
	/**
	 * List containing for each iteration the current best solution's length
	 */
	private LinkedList<Double> bestSolutionsLength;

	/**
	 * List containing for each iteration the current value of the alpha parameter
	 */
	private LinkedList<Double> alphaEvolution;
	
	/**
	 * List containing for each iteration the current value of the total overflow
	 */
	private LinkedList<Double> qEvolution;
	
	/** Creates a new instance of Tabu */
	public Tabu() {
	}

	/**
	 * Optimize a given solution by launching the Tabu algorithm on it
	 * 
	 * @param initSol
	 *            Solution to optimize
	 * @return Final solution optimized by the algorithm
	 */
	public Solution optimizeSolution(Solution initSol) {
		this.currentSol = initSol;
		this.currentSolutionsLength = new LinkedList<Double>();
		this.bestSolutionsLength = new LinkedList<Double>();
		this.alphaEvolution = new LinkedList<Double>();
		this.qEvolution = new LinkedList<Double>();
		
		this.searcher();
		
		return this.currentSol;
	}

	/**
	 * Carries out the search at the highest level
	 */
	public void searcher() {
		Move move;
		int q; // Capacity overflow
		Solution bestSol = null;
		
		while (iters <= Constants.MaxIters) {
			++iters;
			move = generateMove();
			if (move.getCost() == Double.MAX_VALUE) {
				System.out.println("Termination reached early since no better move was possible");
				break;
			}
			currentSol.perform(move);
			makeTabu(move);
			// We update alpha dynamically
			q = currentSol.getQ();
			if(q == 0){Constants.alpha /= (1+Constants.delta);} 
			else {Constants.alpha *= (1+Constants.delta);}
			// And save the current solution if it is the best one ... and realizable
			//if (q == 0 && currentSol.getCost() < this.minCost) {
			if (q == 0 && currentSol.getLength() < this.minLength) {
				currentSol.clearMovesPerformed();
				this.minCost = currentSol.getCost();// move.getCost();
				this.minLength = currentSol.getLength();
				bestSol = currentSol;
			}
			// We log this iteration's values for the best/current solution's length
			currentSolutionsLength.add(currentSol.getLength());
			bestSolutionsLength.add(this.minLength);
			alphaEvolution.add(Constants.alpha); // For debugging purpose
			qEvolution.add(new Double(q)); // For debugging purpose
		}
		//currentSol.generateBestSol();
		currentSol = bestSol;
	}

	/**
	 * Generate the best possible move in the current solution.
	 * Try to move each customer at the best position in the neighbours round
	 * @return Best move to do for the given solution
	 */
	private Move generateMove() {
		Vehicle car = currentSol.getFirstVehicle();
		Customer customer;
		Move move = new Move(Double.MAX_VALUE), auxMove;

		for (int i = 0; i < currentSol.getNumVehicles(); i++) {
			customer = car.getFirstCustomer();
			while (!customer.isDepot()) {
				// Search the best move in the other routes for this customer
				auxMove = bestMove(currentSol.getCost(), minCost, car, customer);
				if (auxMove != null)
					move.updateMove(auxMove);
				customer = customer.getNextCustomer();
			}
			car = car.getNextCar();
		}

		return move;
	}

	/**
	 * Determines whether moving a customer to a new car is tabu or not
	 * @param finalCar New car which will deliver the customer
	 * @param customer Customer we want to move
	 * @return True if the move is tabu
	 */

	static int iDebug = 0;
	private boolean isTabu(Vehicle finalCar, Customer customer) {
		/* TODO Debug a move which do not have customer nor init car
		 * if(finalCar.getId() == 0 && customer.getId() == 49){
			iDebug++;
			System.out.println(iDebug+" => final car "+finalCar.getId()+" / cust "+customer.getId());
			if(iDebug == 880){
				System.out.println("CA VA BUGGUER !");
			}
		}*/
		for (Move tabu : tabuList) {
			if (tabu.getCustomer().getId() == customer.getId()
					&& tabu.getFinalCar().getId() == finalCar.getId()) {
				return true;
			}
		}
		return false;
	}

	/**
	 * Given a customer, this method gives the best move among the adjacent/all
	 * other routes.
	 * @param currentCost Cost of the actual solution
	 * @param currentBest Cost of the actual best solution
	 * @param car Current car containing the customer to Move
	 * @param customer Customer to move in a new round
	 */
	private Move bestMove(double currentCost, double currentBest, Vehicle car, Customer customer) {
		Move move = new Move(Double.MAX_VALUE), moveA;
		// Length decreased by removing the customer from its current round
		double dec = car.inherentDec(customer);
		Vehicle newCar;
		
		/*
		// VERSION 1 : Try only the neighbours rounds
		for (int count = 0; count < 2; count++) {
			if (count == 0)
				newCar = car.getNextCar();
			else
				newCar = car.getPrevCar();

			if(newCar != null){
				moveA = bestPosition(newCar, customer);
				moveA.setNewCost(moveA.getCost() - dec + currentCost); // new value of the cost function
				moveA.setLength(moveA.getLength() - dec); // real value of "delta length"
				if (isTabu(moveA.getFinalCar(), customer)) {
					// Aspiration criteria
					if (moveA.getCost() < currentBest) {
						move.updateMove(moveA);
					}
				} else {
					move.updateMove(moveA);
				}
			}
		}
		*/
		
		// VERSION 2 : Try all the other rounds
		newCar = this.currentSol.getFirstVehicle();
		while(newCar != null){
			if(newCar != car){
				// Find the best position to insert the customer in the current round
				moveA = bestPosition(newCar, customer);
				moveA.setNewCost(moveA.getCost() + this.currentSol.getLength() - dec + this.currentSol.getQ()*Constants.alpha);
				moveA.setLength(moveA.getLength() - dec); // real value of "delta length"
				if (isTabu(moveA.getFinalCar(), customer)) {
					// Aspiration criteria
					if (moveA.getCost() < currentBest) {
						move.updateMove(moveA);
					}
				} else {
					move.updateMove(moveA);
				}
			}
			newCar = newCar.getNextCar();
		}
		
		if(move.getCost() == Double.MAX_VALUE)
			return null;
		move.setCustomer(customer); // which customer
		move.setInitCar(car); // from which car
		return move;
	}

	/**
	 * Given a customer and a vehicle route, this method gives the best place to
	 * put the customer in.
	 * @param newCar Vehicle in which we'd like to insert the current customer
	 * @param customer Customer we'd like to move in the given round
	 */
	private Move bestPosition(Vehicle newCar, Customer customer) {
		int overflow, index = 0;
		double distCh, incCurrent;
		Move move = new Move(Double.MAX_VALUE);
		Customer nextCust, prevCust;

		// Initialize the iteration by taking the first customer 
		// (the prevCust of every first customer has to be the depot)
		nextCust = newCar.getFirstCustomer();
		if(nextCust.isDepot()) return move;
		prevCust = nextCust.getPrevCustomer(); 
		overflow = newCar.overflow(customer.getReq());

		while (!prevCust.isDepot() || index == 0) {
			// Simulates cost and distance changes
			distCh = customer.distanceChange(prevCust, nextCust);
			incCurrent = distCh + Constants.alpha * overflow;
			
			move.updateMove(incCurrent, index, newCar, distCh);
			prevCust = nextCust;
			nextCust = nextCust.getNextCustomer();
			++index;
		}
		return move;
	}

	/**
	 * Append the move to the tabu list (at the end). If the list is full, the first element is removed.
	 * @param move
	 */
	private void makeTabu(Move move) {
		tabuList.addLast(move);
		if (tabuList.size() > Constants.listLength)
			tabuList.remove();
	}

	public LinkedList<Double> getCurrentSolutionsLength() {
		return currentSolutionsLength;
	}

	public LinkedList<Double> getBestSolutionsLength() {
		return bestSolutionsLength;
	}

	public LinkedList<Double> getAlphaEvolution() {
		return alphaEvolution;
	}

	public LinkedList<Double> getQEvolution() {
		return qEvolution;
	}

}
